// https://leetcode.cn/problems/rotate-list/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 计算链表长度并对旋转次数k取模
// 2. 使用快慢指针定位新链表头节点的前驱位置
// 3. 快指针先走k步，然后双指针同步移动至链表末尾
// 4. 断开链表并重新连接，形成旋转后的链表
// 5. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "LinkedListUtils.h"

class Solution 
{
private:
    int GetNodeNums(ListNode* head)
    {
        int ret = 0;
        while (head != nullptr)
        {
            ret++;
            head = head->next;
        }
        return ret;
    }

public:
    ListNode* rotateRight(ListNode* head, int k) 
    {
        if (head == nullptr) return head;

        int nodeNums = GetNodeNums(head);
        k %= nodeNums;

        if (k == 0) return head;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        auto slow = dummy, fast = head;
        while (k--)
        {
            fast = fast->next;
        }

        while (fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }

        auto newHead = slow->next;
        slow->next = nullptr;

        auto link = newHead;
        while (link->next != nullptr)
        {
            link = link->next;
        }
        link->next = head;

        delete dummy;

        return newHead;
    }
};

int main()
{
    vector<int> nodes1 = {1,2,3,4,5};
    vector<int> nodes2 = {0,1,2};
    int k1 = 2, k2 = 4;

    Solution sol;

    auto l1 = createLinkedList(nodes1);
    auto l2 = createLinkedList(nodes2);

    auto r1 = sol.rotateRight(l1, k1);
    auto r2 = sol.rotateRight(l2, k2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}